﻿//给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈
//你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列
//排列：指 1 到 n 每个数字出现且仅出现一次
//
//数据范围：1≤n≤5×10^4，排列中的值都满足1≤val≤n
//进阶：空间复杂度O(n) ，时间复杂度O(n)
//
//输入：
//	[2, 1, 5, 3, 4]
//返回值：
//	[5, 4, 3, 1, 2]
//说明：
//	操作       栈			结果
//	2 入栈；   [2]			[]
//	1 入栈；   [2\1]			[]
//	5 入栈；   [2\1\5]		[]
//	5 出栈；   [2\1]			[5]
//	3 入栈；   [2\1\3]		[5]
//	4 入栈；   [2\1\3\4]		[5]
//	4 出栈；   [2\1\3]		[5, 4]
//	3 出栈；   [2\1]			[5, 4, 3]
//	1 出栈；   [2]			[5, 4, 3, 1]
//	2 出栈；   []			[5, 4, 3, 1, 2]
//
//输入：
//	[1, 2, 3, 4, 5]
//返回值：
//	[5, 4, 3, 2, 1]

class Solution {
public:
    vector<int> solve(vector<int>& a) {
        int n = a.size();
        stack<int> st;
        bool hash[50010] = { 0 }; // 统计当前哪些元素已经进栈
        int aim = n;
        vector<int> ret;
        for (auto x : a) {
            st.push(x);
            hash[x] = true;
            // 先更新⽬标值
            while (hash[aim]) {
                aim--;
            }
            // 出栈
            while (st.size() && st.top() >= aim) {
                ret.push_back(st.top());
                st.pop();
            }
        }
        return ret;
    }
};

